#include <iostream>
#include <queue>


/*
默认是一个大根堆
*/
static void Test01() {
	std::priority_queue<int> pq;

	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);


	// 输出并移除最高优先级的元素
	std::cout << "优先级队列的顶部元素是: " << pq.top() << std::endl;

	pq.pop(); // 移除顶部元素
	std::cout << "移除顶部元素后，新的顶部是: " << pq.top() << std::endl;

}

/*
默认情况下，priority_queue 是一个最大堆。
如果需要最小堆，可以通过自定义比较器或使用 greater 模板来实现。
*/
static void Test02() {
	std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

	minHeap.push(10);
	minHeap.push(30);
	minHeap.push(20);

	std::cout << "最小堆的顶部元素是: " << minHeap.top() << std::endl;

	minHeap.pop();
	std::cout << "移除顶部元素后，新的顶部是: " << minHeap.top() << std::endl;

}

/*
自定义比较器
*/
struct Task {
	int id;
	int priority;

	bool operator<(const Task& other) const{
		return priority < other.priority;
	}
};


static void Test03() {
	std::priority_queue<Task> taskQueue;

	// 插入任务
	taskQueue.push({ 1, 5 });  // id=1, priority=5
	taskQueue.push({ 2, 3 });  // id=2, priority=3
	taskQueue.push({ 3, 8 });  // id=3, priority=8

	while (!taskQueue.empty()) {
		Task task = taskQueue.top();
		std::cout << "任务ID: " << task.id << ", 优先级: " 
			<< task.priority << std::endl;
		taskQueue.pop();

	}

}


struct Task2 {
    int id;
    int priority;
};
// 自定义比较器(写在外面)
struct Task2Compare {
    bool operator()(const Task2& t1, const Task2& t2) const {
        return t1.priority > t2.priority; // 小根堆
    }
};


void Test04() {
    std::priority_queue<Task2, std::vector<Task2>, Task2Compare> taskQueue;

    // 插入任务
    taskQueue.push({ 1, 5 });  // id=1, priority=5
    taskQueue.push({ 2, 3 });  // id=2, priority=3
    taskQueue.push({ 3, 8 });  // id=3, priority=8

    while (!taskQueue.empty()) {
        Task2 task = taskQueue.top();
        std::cout << "任务ID: " << task.id << ", 优先级: "
            << task.priority << std::endl;
        taskQueue.pop();
    }
}


/**
 * STL priority_queue 示例
 * 1. 默认是大根堆
 * 2. 可以通过 std::greater 实现小根堆
 * 3. 可以自定义比较器
 */
int main() {

	//Test01();

	//Test02();

	Test03();

	return 0;
}